package personal.leil.learning.heap;

import personal.leil.learning.utils.ArrayUtils;

/**
 * 堆排序
 * <p>
 * 堆排序代码实现
 * </p>
 *
 * @author Leil
 * @version 1.0
 * @since 2024-1-11
 */
public class HeapSort {


    /**
     * 堆排序实现
     * @param arr   source array
     */
    public static void heapSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        /*
        将数组变成大根堆结构
        heapInsert操作
        时间复杂度为O(NlogN)
         */
//        for (int i = 1; i < arr.length - 1; i++) {
//            heapInsert(arr, i);
//        }
        /*
        将数组变成大根堆结构
        heapify操作
        将数组看作一棵完全二叉树，从最后的叶子节点开始做heapify操作，一直到根节点，则可以得到一个大根堆
        相较于heapInsert的方法，该方式的时间复杂度更低，为O(N)
         */
        for (int i = arr.length - 1; i >= 0; i--) {
            heapify(arr, i, arr.length);
        }
        // 将大根堆的根节点与数组最后一个值交换
        ArrayUtils.swap(arr, 0, arr.length - 1);
        /*
        持续对堆结构数组做如下操作
        ①堆化
        ②交换根和堆结构最后一个数字的值
        ③减小堆结构长度
         */
        int heapSize = arr.length - 1;
        while (heapSize > 0) {
            heapify(arr, 0, heapSize);
            ArrayUtils.swap(arr, 0, --heapSize);
        }
    }

    /**
     * 将数组的前index部分变成大根堆
     * <p>
     * arr[0 ~ index-1]已经为大根堆，将index索引处的数加入，使arr[0 ~ index]变成大根堆
     * </p>
     * @param arr       heap of the largest root for range 0 to index-1 of array
     * @param index     new index
     */
    public static void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {
            ArrayUtils.swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }


    /**
     * 堆化
     * <p>
     * 将本身为大根堆的结构，更改其中的一个节点的值，让其继续变成大根堆
     * </p>
     *
     * @param arr      heap of the largest root
     * @param root     heap root
     * @param heapSize heap size (the length of heap array, not last index)
     */
    public static void heapify(int[] arr, int root, int heapSize) {
        int left = (root << 1) + 1;
        while (left < heapSize) {
            int right = left + 1;
            int maxChild = right < heapSize && arr[left] < arr[right] ? right : left;
            int max = arr[root] > arr[maxChild] ? root : maxChild;
            if (max == root) {
                break;
            }
            ArrayUtils.swap(arr, max, root);
            root = max;
            left = (root << 1) + 1;
        }
    }


    /********************* For Test *************************/


    public static void main(String[] args) {
        int[] arr = ArrayUtils.generateRandomArr(20);
        System.out.println("before sort:");
        ArrayUtils.printArr(arr);
        heapSort(arr);
        System.out.println("after sort:");
        ArrayUtils.printArr(arr);
    }


}
